// 给定一组唯一的单词， 找出所有不同 的索引对(i, j)，使得列表中的两个单词， words[i] + words[j] ，可拼接成回文串。

// 示例 1:

// 输入: ["abcd","dcba","lls","s","sssll"]
// 输出: [[0,1],[1,0],[3,2],[2,4]] 
// 解释: 可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]
// 示例 2:

// 输入: ["bat","tab","cat"]
// 输出: [[0,1],[1,0]] 
// 解释: 可拼接成的回文串为 ["battab","tabbat"]

#include <vector>
#include <string>

using namespace std;

/* 暴力，超时

*/
class Solution {
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        int n = words.size();
        vector<vector<int>> res{};
        for (int i{0}; i < n; ++i) {
            for (int j{0}; j < n; ++j) {
                if (i == j) continue;
                if (isPalindromePairs(words[i] + words[j])) {
                    res.push_back(vector<int>{i, j});
                }
            }
        }
        return res;
    }
    bool isPalindromePairs(const string& s) {
        string s2{s};
        reverse(s2.begin(), s2.end());
        return s == s2;
    }
};

/* 枚举前缀和后缀 - 字典树
设计一个能够在一系列字符串中查询「某个字符串的子串的翻转」是否存在的数据结构，有两种实现方法：
    我们可以使用字典树存储所有的字符串。在进行查询时，我们将待查询串的子串逆序地在字典树上进行遍历，即可判断其是否存在。
    我们可以使用哈希表存储所有字符串的翻转串。在进行查询时，我们判断带查询串的子串是否在哈希表中出现，就等价于判断了其翻转是否存在。
时间复杂度：O(n*m^2)
空间复杂度：O(n*m)
*/
class Solution {
private:
    struct node {
        vector<int> ch{vector<int>(26, 0)};
        int flag{-1};
    };
    vector<node> tree{};
public:
    void insert(string& s, int index) {
        int len = s.size();
        int add{0};
        for (int i{0}; i < len; ++i) {
            int x = s[i] - 'a';
            if (!tree[add].ch[x]) {
                tree.emplace_back();
                tree[add].ch[x] = tree.size() - 1;
            }
            add = tree[add].ch[x];
        }
        tree[add].flag = index;
    }
    bool isPalindrome(const string& s, int left, int right) {
        int len = right - left + 1;
        for (int i{0}; i < len/2; ++i) {
            if (s[left+i] != s[right-i]) {
                return false;
            }
        }
        return true;
    }
    int findWord(const string& s, int left, int right) {
        int add{0};
        for (int i{right}; i >= left; --i) {
            int x = s[i] - 'a';
            if (!tree[add].ch[x]) {
                return -1;
            }
            add = tree[add].ch[x];
        }
        return tree[add].flag;
    }
    vector<vector<int>> palindromePairs(vector<string>& words) {
        tree.emplace_back(node());
        int n = words.size();
        for (int i{0}; i < n; ++i) {
            insert(words[i], i);
        }
        vector<vector<int>> ret{};
        for (int i{0}; i < n; ++i) {
            int m = words[i].size();
            for (int j{0}; j <= m; ++j) {
                if (isPalindrome(words[i], j, m-1)) {
                    int left_id = findWord(words[i], 0, j-1);
                    if (left_id != -1 && left_id != i) {
                        ret.push_back({i, left_id});
                    }
                }
                if (j && isPalindrome(words[i], 0, j-1)) {
                    int right_id = findWord(words[i], j, m-1);
                    if (right_id != -1 && right_id != i) {
                        ret.push_back({right_id, i});
                    }
                }
            }
        }
        return ret;
    }
};

/* 枚举前缀和后缀 - 哈希表
设计一个能够在一系列字符串中查询「某个字符串的子串的翻转」是否存在的数据结构，有两种实现方法：
    我们可以使用字典树存储所有的字符串。在进行查询时，我们将待查询串的子串逆序地在字典树上进行遍历，即可判断其是否存在。
    我们可以使用哈希表存储所有字符串的翻转串。在进行查询时，我们判断带查询串的子串是否在哈希表中出现，就等价于判断了其翻转是否存在。
时间复杂度：O(n*m^2)
空间复杂度：O(n*m)
*/
class Solution {
private:
    vector<string> wordsRev{}; // 反转字符串
    unordered_map<string_view, int> indices{};
public:
    bool isPalindrome(const string_view& s, int left, int right) {
        int len = right - left + 1;
        for (int i{0}; i < len/2; ++i) {
            if (s[left+i] != s[right-i]) {
                return false;
            }
        }
        return true;
    }
    int findWord(const string_view& s, int left, int right) {
        auto iter = indices.find(s.substr(left, right-left+1));
        return iter == indices.end() ? -1 : iter->second;
    }
    vector<vector<int>> palindromePairs(vector<string>& words) {
        int n = words.size();
        for (const string& word : words) {
            wordsRev.push_back(word);
            reverse(wordsRev.back().begin(), wordsRev.back().end());
        }
        for (int i{0}; i < n; ++i) {
            indices.emplace(wordsRev[i], i);
        }
        vector<vector<int>> ret{};
        for (int i{0}; i < n; ++i) {
            int m = words[i].size();
            if (m == 0) continue;
            string_view wordView(words[i]);
            for (int j{0}; j <= m; ++j) {
                if (isPalindrome(wordView, j, m-1)) { // 前一段
                    int left_id = findWord(wordView, 0, j-1);
                    if (left_id != -1 && left_id != i) {
                        ret.push_back({i, left_id});
                    }
                }
                if (j && isPalindrome(wordView, 0, j-1)) { // 后一段
                    int right_id = findWord(wordView, j, m-1);
                    if (right_id != -1 && right_id != i) {
                        ret.push_back({right_id, i});
                    }
                }
            }
        }
        return ret;
    }
};

/* 字典树 + manacher
时间复杂度：O(n*m)
空间复杂度：O(n*m)
*/
struct Trie {
    struct node {
        int ch[26];
        int flag;
        node() {
            flag = -1;
            memset(ch, 0, sizeof(ch));
        }
    };

    vector<node> tree;

    Trie() { tree.emplace_back(); }

    void insert(string& s, int id) {
        int len = s.length(), add = 0;
        for (int i = 0; i < len; i++) {
            int x = s[i] - 'a';
            if (!tree[add].ch[x]) {
                tree.emplace_back();
                tree[add].ch[x] = tree.size() - 1;
            }
            add = tree[add].ch[x];
        }
        tree[add].flag = id;
    }

    vector<int> query(string& s) {
        int len = s.length(), add = 0;
        vector<int> ret(len + 1, -1);
        for (int i = 0; i < len; i++) {
            ret[i] = tree[add].flag;
            int x = s[i] - 'a';
            if (!tree[add].ch[x]) {
                return ret;
            }
            add = tree[add].ch[x];
        }
        ret[len] = tree[add].flag;
        return ret;
    }
};

class Solution {
public:
    vector<pair<int, int>> manacher(string& s) {
        int n = s.length();
        string tmp = "#";
        tmp += s[0];
        for (int i = 1; i < n; i++) {
            tmp += '*';
            tmp += s[i];
        }
        tmp += '!';
        int m = n * 2;
        vector<int> len(m);
        vector<pair<int, int>> ret(n);
        int p = 0, maxn = -1;
        for (int i = 1; i < m; i++) {
            len[i] = maxn >= i ? min(len[2 * p - i], maxn - i) : 0;
            while (tmp[i - len[i] - 1] == tmp[i + len[i] + 1]) {
                len[i]++;
            }
            if (i + len[i] > maxn) {
                p = i, maxn = i + len[i];
            }
            if (i - len[i] == 1) {
                ret[(i + len[i]) / 2].first = 1;
            }
            if (i + len[i] == m - 1) {
                ret[(i - len[i]) / 2].second = 1;
            }
        }
        return ret;
    }

    vector<vector<int>> palindromePairs(vector<string>& words) {
        Trie trie1, trie2;

        int n = words.size();
        for (int i = 0; i < n; i++) {
            trie1.insert(words[i], i);
            string tmp = words[i];
            reverse(tmp.begin(), tmp.end());
            trie2.insert(tmp, i);
        }

        vector<vector<int>> ret;
        for (int i = 0; i < n; i++) {
            const vector<pair<int, int>>& rec = manacher(words[i]);

            const vector<int>& id1 = trie2.query(words[i]);
            reverse(words[i].begin(), words[i].end());
            const vector<int>& id2 = trie1.query(words[i]);

            int m = words[i].size();

            int all_id = id1[m];
            if (all_id != -1 && all_id != i) {
                ret.push_back({i, all_id});
            }
            for (int j = 0; j < m; j++) {
                if (rec[j].first) {
                    int left_id = id2[m - j - 1];
                    if (left_id != -1 && left_id != i) {
                        ret.push_back({left_id, i});
                    }
                }
                if (rec[j].second) {
                    int right_id = id1[j];
                    if (right_id != -1 && right_id != i) {
                        ret.push_back({i, right_id});
                    }
                }
            }
        }
        return ret;
    }
};